package sample.xiaosong.binaryTree;

import java.util.*;

/**
 * @author xiaosong
 */
public class BinaryTreeFunc {

    public static class Node {
        public String value;
        public Node left;
        public Node right;
        public Node parent;
        public int intValue;

        public Node(String data) {
            this.value = data;
        }

        public Node(int data) {
            this.intValue = data;
        }
    }

    /**
     * 二叉树的先序遍历 递归版
     * @param head 头结点
     */
    public static void preOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        System.out.println(head.value);
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    /**
     * 二叉树的中序遍历 递归版
     * @param head 头结点
     */
    public static void inOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        inOrderRecur(head.left);
        System.out.println(head.value);
        inOrderRecur(head.right);
    }

    /**
     * 二叉树的后序遍历 递归版
     * @param head 头结点
     */
    public static void postOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        postOrderRecur(head.left);
        postOrderRecur(head.right);
        System.out.println(head.value);
    }

    /**
     * 二叉树的前序遍历 非递归版
     * @param head 头节点
     */
    public static void preOrderUnRecur(Node head) {
        System.out.print("preOrderUnRecur: ");
        if (head != null) {
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.println(head.value);
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
    }

    /**
     * 二叉树的中序遍历 非递归版
     * @param head 头节点
     */
    public static void inOrderUnRecur(Node head) {
        System.out.print("inOrderUnRecur: ");
        Stack<Node> stack = new Stack<>();
        if (head != null) {
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.println(head.value);
                    head = head.right;
                }
            }
        }
    }

    /**
     * 二叉树的后序遍历 非递归版1
     * @param head 头节点
     */
    public static void postOrderUnRecur1(Node head) {
        System.out.println("postOrderUnRecur1: ");
        if (head != null) {
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            stack1.push(head);
            while (!stack1.isEmpty()) {
                head = stack1.pop();
                stack2.push(head);
                if (head.left != null) {
                    stack1.push(head.left);
                }
                if (head.right != null) {
                    stack1.push(head.right);
                }
            }
            while (!stack2.isEmpty()) {
                System.out.println(stack2.pop().value);
            }
        }
    }

    /**
     * 二叉树的后序遍历 非递归版2
     * @param head 头节点
     */
    public static void postOrderUnRecur2(Node head) {
        System.out.println("postOrderUnRecur1: ");
        if (head != null) {
            Stack<Node> stack = new Stack<>();
            Node n = null;
            stack.push(head);
            while (!stack.isEmpty()) {
                n = stack.peek();
                if (n.left != null && head != n.left && head != n.right) {
                    stack.push(n.left);
                } else if (n.right != null && head != n.right) {
                    stack.push(n.right);
                } else {
                    System.out.println(stack.pop().value);
                    head = n;
                }
            }
        }
    }

    /**
     * 获取二叉树的最大宽度 宽度优先遍历
     * @param head 头节点
     * @return 最大宽度值
     */
    public static int getWidth(Node head) {
        if (head == null) {
            return 0;
        }
        Map<Node, Integer> levelMap = new HashMap<>();
        levelMap.put(head, 1);
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(head);
        int curWidth = 0;
        int curLevel = 0;
        int maxWidth = 0;
        while (!queue.isEmpty()) {
            head = queue.poll();
            Node left = head.left;
            Node right = head.right;
            if (left != null) {
                levelMap.put(left, levelMap.get(head) + 1);
                queue.add(left);
            }
            if (right != null) {
                levelMap.put(right, levelMap.get(head) + 1);
                queue.add(right);
            }
            if (levelMap.get(head) > curLevel) {
                curWidth = 0;
                curLevel = levelMap.get(head);
            } else {
                curWidth++;
            }
            maxWidth = Math.max(maxWidth, curWidth);
        }
        return maxWidth;
    }

    /**
     * 验证二叉树是否是搜索二叉树   tips: 满足中序遍历从小到大排序
     * @param head 头节点
     * @return TRUE or FALSE
     */
    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> inOrderList = new LinkedList<>();
        bstProcess(inOrderList, head);
        int pre = Integer.MIN_VALUE;
        for (Node node : inOrderList) {
            if (node.intValue > pre) {
                return false;
            }
            pre = node.intValue;
        }
        return true;
    }

    private static void bstProcess(LinkedList<Node> inOrderList, Node head) {
        if (head == null) {
            return;
        }
        bstProcess(inOrderList, head.left);
        inOrderList.add(head);
        bstProcess(inOrderList, head.right);
    }

    /**
     * 验证二叉树是否为完全二叉树   tips:完全二叉树除最深层外，都为满节点，最深一层所有节点靠左
     * @param head 头节点
     * @return TRUE or FALSE
     */
    public static boolean isCBT(Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(head);
        Node left = null;
        Node right = null;
        boolean flag = false;
        while (!queue.isEmpty()) {
            head = queue.poll();
            left = head.left;
            right = head.right;
            // flag 为第一个没有右节点的节点，说明已经到了最后一层
            if ((flag && (left != null || right != null)) || (left == null && right != null)) {
                return false;
            }
            if (left != null) {
                queue.add(left);
            }
            if (right != null) {
                queue.add(right);
            } else {
                flag = true;
            }
        }
        return true;
    }

    /**
     * 判断二叉树是否为平衡二叉树   tips:平衡二叉树的左右高度差不能大于1，且所有子树均为平衡二叉树
     * @param head 头节点
     * @return TRUE or FALSE
     */
    public static boolean isBalance(Node head) {
        if (head == null) {
            return true;
        }
        return balanceTreeProcess(head).isBalanced;
    }

    public static BalanceTreeInfo balanceTreeProcess(Node head) {
        if (head == null) {
            return new BalanceTreeInfo(true, 0);
        }
        BalanceTreeInfo leftData = balanceTreeProcess(head.left);
        BalanceTreeInfo rightData = balanceTreeProcess(head.right);
        // 计算当前节点的高度
        int height = Math.max(leftData.height, rightData.height) + 1;
        // 判断子树是否平衡 以及 左右树高度差是否大于1
        boolean isBalance = leftData.isBalanced && rightData.isBalanced
                && Math.abs(leftData.height - rightData.height) > 2;
        return new BalanceTreeInfo(isBalance, height);
    }

    /**
     * 平衡二叉树节点信息
     */
    public static class BalanceTreeInfo {
        public boolean isBalanced;
        public int height;

        public BalanceTreeInfo(boolean isB, int hei) {
            isBalanced = isB;
            height = hei;
        }
    }

    /**
     * 对于任意两个二叉树的节点 寻找他们的最小公共祖先
     * @param head 头节点
     * @param n1 节点1
     * @param n2 节点2
     * @return 最小公共祖先
     */
    public static Node getLowestAncestor(Node head, Node n1, Node n2) {
        // 找到叶子节点 或者 找到 n1 n2时直接返回
        if (head == null || head == n1 || head == n2) {
            return head;
        }
        Node left = getLowestAncestor(head.left, n1, n2);
        Node right = getLowestAncestor(head.right, n1, n2);
        // 某个节点的左右返回值都不为空时，即为最小公共祖先
        if (left != null && right != null) {
            return head;
        }
        // 返回节点值(如果找到了n1 n2节点，依次往上返回；如果没找到往上返回null)
        return left != null ? left : right;
    }

    /**
     * 对于二叉树的任一节点，返回他的后继节点   tips:parent为节点的父节点，后继节点为中序遍历中的后一个节点
     * @param node 二叉树中任一节点
     * @return 该节点的后继节点
     */
    public static Node getSuccessorNode(Node node) {
        if (node == null) {
            return null;
        }
        //如果该节点存在右子树，那么后继节点为右子树的最左节点
        if (node.right != null) {
            return getLeftMost(node);
        } else {
            Node parent = node.parent;
            //如果该节点只有左子树，那么后继节点为头节点 或者 该节点的父节点
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    /**
     * 获取子树最左节点
     * @param node 任一节点
     * @return 最左侧节点
     */
    private static Node getLeftMost(Node node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * 把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后 展开。
     * 此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。
     * 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，
     * 从 上到下依次是下折痕、下折痕和上折痕。
     * 给定一个输入参数N，代表纸条都从下边向上方连续对折N次。
     * 打印出纸条从上到下的折痕
     * @param n 折叠次数
     */
    public static void printAllFolds(int n) {
        printProcess(1, n, true);
    }

    /**
     * 实际上为二叉树的中序遍历。
     * 假定第一个凹折痕为头节点，折一次之后，上方凹折痕为左节点，下方凸折痕为右节点
     * 以此类推，可以构成一个左节点为凹，右节点为凸的满二叉树
     * @param i 当前为第i次折叠
     * @param N 一共折叠了N次
     * @param down 是否为凹节点
     */
    private static void printProcess(int i, int N, boolean down) {
        if (i > N) {
            return;
        }
        printProcess(i + 1, N, true);
        System.out.println(down ? "凹" : "凸");
        printProcess(i + 1, N, false);
    }

    public static void main(String[] args) {
        Node head = new Node("A");
        head.left = new Node("B");
        head.right = new Node("C");
        head.left.left = new Node("D");
        head.left.right = new Node("E");
        head.left.left.left = new Node("H");
        head.left.right.right = new Node("I");

        head.right.left = new Node("F");
        head.right.left.right = new Node("J");
        head.right.right = new Node("G");
        head.right.right.left = new Node("K");

        // recursive
        System.out.println("==============recursive==============");
        System.out.print("pre-order: ");
        preOrderRecur(head);
        System.out.println();
        System.out.print("in-order: ");
        inOrderRecur(head);
        System.out.println();
        System.out.print("pos-order: ");
        postOrderRecur(head);
        System.out.println();

        System.out.println("============unrecursive=============");
        preOrderUnRecur(head);
        inOrderUnRecur(head);
        postOrderUnRecur1(head);
        postOrderUnRecur2(head);

        System.out.println("============getWidth=============");
        System.out.println(getWidth(head));

        System.out.println("============NumberValueTree=============");
        Node head1 = new Node(1);
        head1.parent = null;
        head1.left = new Node(2);
        head1.left.parent = head1;
        head1.right = new Node(3);
        head1.right.parent = head1;
        head1.left.left = new Node(4);
        head1.left.left.parent = head1.left;
        head1.left.right = new Node(5);
        head1.left.right.parent = head1.left;
        head1.left.left.left = new Node(8);
        head1.left.left.left.parent = head1.left.left;
        head1.left.right.right = new Node(9);
        head1.left.right.right.parent = head1.left.right;

        head1.right.left = new Node(6);
        head1.right.left.parent = head1.right;
        head1.right.left.right = new Node(10);
        head1.right.left.right.parent = head1.right.left;
        head1.right.right = new Node(7);
        head1.right.right.parent = head1.right;
        head1.right.right.left = new Node(11);
        head1.right.right.left.parent = head1.right.right;

        System.out.println("isBST: " + isBST(head1));
        System.out.println("isCBT: " + isCBT(head1));
        System.out.println("isBalance: " + isBalance(head1));

        Node n1 = head1.right.left.right;
        Node n2 = head1.left.right.right;
        System.out.println("getLowestAncestor: " + getLowestAncestor(head1, n1, n2).intValue);

        System.out.println("============SuccessorNode=============");
        Node test = head1.left.left;
        System.out.println(test.intValue + " next: " + getSuccessorNode(test).intValue);
        test = head1.left.right.right;
        System.out.println(test.intValue + " next: " + getSuccessorNode(test).intValue);
        test = head1.right.left.right;
        System.out.println(test.intValue + " next: " + getSuccessorNode(test).intValue);


        System.out.println("============PaperFolding=============");
        printAllFolds(3);
    }
}
